{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Range Sum of Sorted Subarray Sums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rangeSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组和排序后的区间和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>nums</code>&nbsp;，它包含&nbsp;<code>n</code>&nbsp;个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含&nbsp;<code>n * (n + 1) / 2</code>&nbsp;个数字的数组。</p>\n",
    "\n",
    "<p>请你返回在新数组中下标为<em>&nbsp;</em><code>left</code>&nbsp;到&nbsp;<code>right</code> <strong>（下标从 1 开始）</strong>的所有数字和（包括左右端点）。由于答案可能很大，请你将它对 10^9 + 7 取模后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4], n = 4, left = 1, right = 5\n",
    "<strong>输出：</strong>13 \n",
    "<strong>解释：</strong>所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4], n = 4, left = 3, right = 4\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4], n = 4, left = 1, right = 10\n",
    "<strong>输出：</strong>50\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10^3</code></li>\n",
    "\t<li><code>nums.length == n</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= left &lt;= right&nbsp;&lt;= n * (n + 1) / 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [range-sum-of-sorted-subarray-sums](https://leetcode.cn/problems/range-sum-of-sorted-subarray-sums/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [range-sum-of-sorted-subarray-sums](https://leetcode.cn/problems/range-sum-of-sorted-subarray-sums/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n4\\n1\\n5', '[1,2,3,4]\\n4\\n3\\n4', '[1,2,3,4]\\n4\\n1\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        def visit(root):\n",
    "          nonlocal res\n",
    "          if not root:\n",
    "            return\n",
    "          if root.val < low:\n",
    "            visit(root.right)\n",
    "          elif root.val > high:\n",
    "            visit(root.left)\n",
    "          else:\n",
    "            res += root.val\n",
    "            visit(root.left)\n",
    "            visit(root.right)\n",
    "        \n",
    "        visit(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        if L <= root.val <= R:\n",
    "            root.left = self.rangeSumBST(root.left, L, R)\n",
    "            root.right = self.rangeSumBST(root.right, L, R)\n",
    "            res += root.val\n",
    "        elif root.val < L:\n",
    "            root.right = self.rangeSumBST(root.right, L, R)\n",
    "            root.left = 0\n",
    "        else:\n",
    "            root.left = self.rangeSumBST(root.left, L, R)\n",
    "            root.right = 0\n",
    "\n",
    "        return res+root.left+root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import LifoQueue\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        result = 0\n",
    "        heap = LifoQueue()\n",
    "        heap.put(root)\n",
    "        while heap.qsize() != 0:\n",
    "            _root = heap.get()\n",
    "            if _root is None:\n",
    "                continue\n",
    "            if _root.left is None and _root.right is None:\n",
    "                if low <= _root.val <= high:\n",
    "                    result += _root.val\n",
    "                continue\n",
    "            _right = _root.right\n",
    "            _left = _root.left\n",
    "            _root.left = None\n",
    "            _root.right = None\n",
    "            if _root.val < high and _right is not None:\n",
    "                heap.put(_right)\n",
    "            if low <= _root.val <= high:\n",
    "                heap.put(_root)\n",
    "                _root.left = None\n",
    "                _root.right = None\n",
    "            if _root.val > low and _left is not None:\n",
    "                heap.put(_left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        def recursion(node):\n",
    "            if node: \n",
    "                if node.val >= L: recursion(node.left)        \n",
    "                if L <= node.val <= R: self.res += node.val                \n",
    "                if node.val <= R: recursion(node.right)\n",
    "        \n",
    "        self.res = 0\n",
    "        recursion(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.val < L:\n",
    "            return self.rangeSumBST(root.right, L, R)\n",
    "        if root.val > R:\n",
    "            return self.rangeSumBST(root.left, L, R)\n",
    "        res = root.val\n",
    "        res += self.rangeSumBST(root.left, L, R)\n",
    "        res += self.rangeSumBST(root.right, L, R)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        ret = 0\n",
    "        if root:\n",
    "            if L <= root.val <= R:\n",
    "                ret = root.val\n",
    "            if root.val <= R:\n",
    "                ret += self.rangeSumBST(root.right, L, R)\n",
    "            if root.val >= L:\n",
    "                ret += self.rangeSumBST(root.left, L, R)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        cur, stack, res = root, [], []\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            node = stack.pop()\n",
    "            if node.val >= L and node.val <= R:\n",
    "                res.append(node.val)\n",
    "            cur = node.right\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        stack = []\n",
    "        current = root\n",
    "        sum = 0\n",
    "        while current or len(stack)>0:\n",
    "            while current.left:\n",
    "                stack.append(current)\n",
    "                current = current.left\n",
    "                stack[-1].left = None\n",
    "            if current.val > high:\n",
    "                break\n",
    "            if current.val >= low:\n",
    "                sum += current.val\n",
    "            if current.right:\n",
    "                current = current.right\n",
    "            elif len(stack)>0:\n",
    "                current = stack.pop()\n",
    "            else:\n",
    "                break\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        self.sum=0\n",
    "        self.inorder(root,low,high)\n",
    "        return self.sum\n",
    "    def inorder(self,root,low,high):\n",
    "        if not root:\n",
    "            return \n",
    "        if root:\n",
    "            self.inorder(root.left,low,high)\n",
    "            if  root.val<low:\n",
    "                root.left=None\n",
    "            elif root.val>high:\n",
    "                root.right=None\n",
    "            else: \n",
    "                self.sum+=root.val\n",
    "            self.inorder(root.right,low,high)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def rangeSumBST(self, root, low: int, high: int) -> int:\r\n",
    "        res = 0\r\n",
    "        cur = root\r\n",
    "        while cur:\r\n",
    "            if cur.val < low:\r\n",
    "                cur.left = None\r\n",
    "            elif cur.val > high:\r\n",
    "                cur.right = None\r\n",
    "            if cur.left is None:\r\n",
    "                if cur.val >= low and cur.val <= high:\r\n",
    "                    res += cur.val\r\n",
    "                cur = cur.right\r\n",
    "            else:\r\n",
    "                max_right = cur.left\r\n",
    "                while max_right.right is not None and max_right.right != cur:\r\n",
    "                    max_right = max_right.right\r\n",
    "                if max_right.right is None:\r\n",
    "                    max_right.right = cur\r\n",
    "                    cur = cur.left\r\n",
    "                else:\r\n",
    "                    max_right.right = None\r\n",
    "                    if cur.val >= low and cur.val <= high:\r\n",
    "                        res += cur.val\r\n",
    "                    cur = cur.right\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:\n",
    "        from queue import Queue\n",
    "        node_queue = Queue()\n",
    "        node_queue.put(root)\n",
    "        cnt = 0\n",
    "        while not node_queue.empty():\n",
    "            node = node_queue.get()\n",
    "            if node is not None:\n",
    "                if node.val is not None and L <= node.val <= R:\n",
    "                    cnt += node.val\n",
    "                if node.left is not None:\n",
    "                    node_queue.put(node.left)\n",
    "                if node.right is not None:\n",
    "                    node_queue.put(node.right)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        if not root: return 0\n",
    "        if  root.val > high:\n",
    "            return self.rangeSumBST(root.left,low,high)\n",
    "        if root.val < low:\n",
    "            return self.rangeSumBST(root.right,low,high)\n",
    "        return root.val + self.rangeSumBST(root.left,low,high) + self.rangeSumBST(root.right,low,high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        x=[root]\n",
    "        s=0\n",
    "        while x:\n",
    "            t=x.pop()\n",
    "            if not t:\n",
    "                continue\n",
    "            if t.val>high:\n",
    "                x.append(t.left)\n",
    "            elif t.val<low:\n",
    "                x.append(t.right)\n",
    "            else:\n",
    "                s+=t.val\n",
    "                x.append(t.left)\n",
    "                x.append(t.right)\n",
    "        return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        leftSum = self.rangeSumBST(root.left,low,high)\n",
    "        rightSum = self.rangeSumBST(root.right,low,high)\n",
    "        result =leftSum+rightSum\n",
    "        if root.val>=low and root.val<=high:\n",
    "            result += root.val\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        self.cur = 0\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            if node.val > high:\n",
    "                return\n",
    "            if node.val >= low:\n",
    "                self.cur += node.val\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        # 中序遍历二叉搜索树等于遍历有序数组\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.val > high:\n",
    "            return self.rangeSumBST(root.left,low,high)\n",
    "        elif root.val < low: #搜索树，左子树全部节点值小于又子树,全部抛弃\n",
    "            return self.rangeSumBST(root.right,low,high)\n",
    "        else:\n",
    "            return self.rangeSumBST(root.left,low,high) + root.val + self.rangeSumBST(root.right,low,high)\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root.val < low:\n",
    "            return self.rangeSumBST(root.right , low , high)\n",
    "        if root.val >high:\n",
    "            return self.rangeSumBST(root.left , low , high)\n",
    "        return root.val + self.rangeSumBST(root.left , low , high) + self.rangeSumBST(root.right , low , high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        cur=root\n",
    "        nums=[]\n",
    "        def dfs(cur):\n",
    "            if low<=cur.val<=high:\n",
    "                nums.append(cur.val)\n",
    "            if cur.left:\n",
    "                dfs(cur.left)\n",
    "            if cur.right:\n",
    "                dfs(cur.right)\n",
    "        dfs(cur)\n",
    "        return sum(nums) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:\n",
    "        stack = [root]\n",
    "        visited =set()\n",
    "        ans = 0\n",
    "        while len(stack) != 0:\n",
    "            tail = stack[-1]\n",
    "            if tail.left is not None and tail.left not in visited:\n",
    "                stack.append(tail.left)\n",
    "            else:\n",
    "                stack.pop()\n",
    "                visited.add(tail)\n",
    "                if tail.val > high:\n",
    "                    return ans\n",
    "                if tail.val >= low:\n",
    "                    ans+=tail.val \n",
    "                if tail.right is not None:\n",
    "                    stack.append(tail.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        if root.val < low:\n",
    "            return self.rangeSumBST(root.right, low, high)\n",
    "        elif root.val > high:\n",
    "            return self.rangeSumBST(root.left, low, high)\n",
    "        else:\n",
    "            return root.val \\\n",
    "                    + self.rangeSumBST(root.left, low, high) \\\n",
    "                    + self.rangeSumBST(root.right, low, high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root.val > high:\n",
    "            return self.rangeSumBST(root.left, low, high)\n",
    "        if root.val < low:\n",
    "            return self.rangeSumBST(root.right, low, high)\n",
    "        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "\n",
    "        mod = int(1e9+7)\n",
    "\n",
    "        # 前缀和数组\n",
    "\n",
    "        sums = [0 for _ in range(n+1)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "\n",
    "            sums[i] = sums[i-1] + nums[i-1]\n",
    "\n",
    "        # 看作 以nums[i]为起点 的n个子数组序列 进行多路归并\n",
    "\n",
    "        pq = []\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            # (val, i, idx)代表前缀和数值, 以第i个数为起点, 到第idx个数为终点\n",
    "\n",
    "            # 加入 每个元素 作为n个子数组序列的起始数组\n",
    "\n",
    "            heappush(pq, (nums[i], i, i))\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for j in range(1, right+1):\n",
    "\n",
    "            val, i, idx = heappop(pq)\n",
    "\n",
    "            if idx + 2 <= n:\n",
    "\n",
    "                heappush(pq, (sums[idx+2] - sums[i], i, idx+1))\n",
    "\n",
    "            if j >= left:\n",
    "\n",
    "                res += val\n",
    "\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "\n",
    "        mod = int(1e9+7)\n",
    "\n",
    "        # 前缀和数组\n",
    "\n",
    "        sums = [0 for _ in range(n+1)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "\n",
    "            sums[i] = sums[i-1] + nums[i-1]\n",
    "\n",
    "        # 看作 以nums[i]为起点 的n个子数组序列 进行多路归并\n",
    "\n",
    "        pq = []\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            # (val, i, idx)代表前缀和数值, 以第i个数为起点, 到第idx个数为终点\n",
    "\n",
    "            # 加入 每个元素 作为n个子数组序列的起始数组\n",
    "\n",
    "            heappush(pq, (nums[i], i, i))\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for j in range(1, right+1):\n",
    "\n",
    "            val, i, idx = heappop(pq)\n",
    "\n",
    "            if idx + 2 <= n:\n",
    "\n",
    "                heappush(pq, (sums[idx+2] - sums[i], i, idx+1))\n",
    "\n",
    "            if j >= left:\n",
    "\n",
    "                res += val\n",
    "\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        prefixSums = [0]\n",
    "        for i in range(n):\n",
    "            prefixSums.append(prefixSums[-1] + nums[i])\n",
    "        \n",
    "        prefixPrefixSums = [0]\n",
    "        for i in range(n):\n",
    "            prefixPrefixSums.append(prefixPrefixSums[-1] + prefixSums[i + 1])\n",
    "\n",
    "        def getCount(x: int) -> int:\n",
    "            count = 0\n",
    "            j = 1\n",
    "            # 遍历虚拟矩阵的每一层，统计满足条件的个数\n",
    "            for i in range(n):\n",
    "\t            # i 在不断增长，所以 prefixSums[i] 一直表示都是当前层的第一个元素\n",
    "                while j <= n and prefixSums[j] - prefixSums[i] <= x:\n",
    "\t                # 符合条件就右移\n",
    "                    j += 1\n",
    "                j -= 1\n",
    "                count += j - i\n",
    "            return count\n",
    "\n",
    "        def getKth(k: int) -> int:\n",
    "\t        # 这里整个二分查找就是求左边界\n",
    "\t\t\t# 即找到第一个满足 count == k 的值（使count == k的最小值）\n",
    "            left, right = 0, prefixSums[n]\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                count = getCount(mid)\n",
    "                if count < k:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "\n",
    "        def getSum(k: int) -> int:\n",
    "            num = getKth(k)\n",
    "            total, count = 0, 0\n",
    "            j = 1\n",
    "            # 遍历“虚拟矩阵”的每一层\n",
    "            for i in range(n):\n",
    "                while j <= n and prefixSums[j] - prefixSums[i] < num:\n",
    "                    j += 1\n",
    "                # 当前 j 位置的元素是 i 行 第 1 个大于等于 num 的值\n",
    "                # 我们要找的是最后一个小于 num 的元素，所以 -1\n",
    "                # 确定区间的右边界 j\n",
    "                j -= 1\n",
    "\n",
    "                # 计算区间和\n",
    "                total += prefixPrefixSums[j] - prefixPrefixSums[i] - prefixSums[i] * (j - i)\n",
    "                # 记录当前行符合条件的个数\n",
    "                count += j - i\n",
    "\t        # 最后补上等于 num 的部分\n",
    "            total += num * (k - count)\n",
    "            return total\n",
    "\n",
    "        return (getSum(right) - getSum(left - 1)) % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        prefixSums = [0]\n",
    "        for i in range(n):\n",
    "            prefixSums.append(prefixSums[-1] + nums[i])\n",
    "        \n",
    "        prefixPrefixSums = [0]\n",
    "        for i in range(n):\n",
    "            prefixPrefixSums.append(prefixPrefixSums[-1] + prefixSums[i + 1])\n",
    "\n",
    "        def getCount(x: int) -> int:\n",
    "            count = 0\n",
    "            j = 1\n",
    "            for i in range(n):\n",
    "                while j <= n and prefixSums[j] - prefixSums[i] <= x:\n",
    "                    j += 1\n",
    "                j -= 1\n",
    "                count += j - i\n",
    "            return count\n",
    "\n",
    "        def getKth(k: int) -> int:\n",
    "            low, high = 0, prefixSums[n]\n",
    "            while low < high:\n",
    "                mid = (low + high) // 2\n",
    "                count = getCount(mid)\n",
    "                if count < k:\n",
    "                    low = mid + 1\n",
    "                else:\n",
    "                    high = mid\n",
    "            return low\n",
    "\n",
    "        def getSum(k: int) -> int:\n",
    "            num = getKth(k)\n",
    "            total, count = 0, 0\n",
    "            j = 1\n",
    "            for i in range(n):\n",
    "                while j <= n and prefixSums[j] - prefixSums[i] < num:\n",
    "                    j += 1\n",
    "                j -= 1\n",
    "                total += prefixPrefixSums[j] - prefixPrefixSums[i] - prefixSums[i] * (j - i)\n",
    "                count += j - i\n",
    "            total += num * (k - count)\n",
    "            return total\n",
    "\n",
    "        return (getSum(right) - getSum(left - 1)) % MODULO\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        # 前缀和数组\n",
    "        sums = [0 for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            sums[i] = sums[i-1] + nums[i-1]\n",
    "        # 看作 以nums[i]为起点 的n个子数组序列 进行多路归并\n",
    "        pq = []\n",
    "        for i in range(n):\n",
    "            # (val, i, idx)代表前缀和数值, 以第i个数为起点, 到第idx个数为终点\n",
    "            # 加入 每个元素 作为n个子数组序列的起始数组\n",
    "            heappush(pq, (nums[i], i, i))\n",
    "        res = 0\n",
    "        for j in range(1, right+1):\n",
    "            val, i, idx = heappop(pq)\n",
    "            if idx + 2 <= n:\n",
    "                heappush(pq, (sums[idx+2] - sums[i], i, idx+1))\n",
    "            if j >= left:\n",
    "                res += val\n",
    "        return res % mod\n",
    "\n",
    "\n",
    "\n",
    "# 二分查找 + 双指针 ？\n",
    "# O(nlogS) O(n)\n",
    "# https://leetcode.cn/problems/range-sum-of-sorted-subarray-sums/solution/zi-shu-zu-he-pai-xu-hou-de-qu-jian-he-by-leetcode-/\n",
    "# https://leetcode.cn/problems/range-sum-of-sorted-subarray-sums/solution/-by-mkdir700-l90o/\n",
    "class Solution2:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        prefixSums = [0]\n",
    "        for i in range(n):\n",
    "            prefixSums.append(prefixSums[-1] + nums[i])\n",
    "        \n",
    "        prefixPrefixSums = [0]\n",
    "        for i in range(n):\n",
    "            prefixPrefixSums.append(prefixPrefixSums[-1] + prefixSums[i + 1])\n",
    "\n",
    "        def getCount(x: int) -> int:\n",
    "            count = 0\n",
    "            j = 1\n",
    "            # 遍历虚拟矩阵的每一层，统计满足条件的个数\n",
    "            for i in range(n):\n",
    "\t            # i 在不断增长，所以 prefixSums[i] 一直表示都是当前层的第一个元素\n",
    "                while j <= n and prefixSums[j] - prefixSums[i] <= x:\n",
    "\t                # 符合条件就右移\n",
    "                    j += 1\n",
    "\n",
    "                j -= 1\n",
    "                count += j - i\n",
    "\n",
    "            return count\n",
    "\n",
    "\n",
    "        def getKth(k: int) -> int:\n",
    "\t        # 这里整个二分查找就是求左边界\n",
    "\t\t\t# 即找到第一个满足 count == k 的值（使count == k的最小值）\n",
    "            left, right = 0, prefixSums[n]\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                count = getCount(mid)\n",
    "                if count < k:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "\n",
    "            return left\n",
    "\n",
    "\n",
    "        def getSum(k: int) -> int:\n",
    "            num = getKth(k)\n",
    "            total, count = 0, 0\n",
    "            j = 1\n",
    "            # 遍历“虚拟矩阵”的每一层\n",
    "            for i in range(n):\n",
    "                while j <= n and prefixSums[j] - prefixSums[i] < num:\n",
    "                    j += 1\n",
    "\n",
    "                # 当前 j 位置的元素是 i 行 第 1 个大于等于 num 的值\n",
    "                # 我们要找的是最后一个小于 num 的元素，所以 -1\n",
    "                # 确定区间的右边界 j\n",
    "                j -= 1\n",
    "\n",
    "                # 计算区间和\n",
    "                total += prefixPrefixSums[j] - prefixPrefixSums[i] - prefixSums[i] * (j - i)\n",
    "                # 记录当前行符合条件的个数\n",
    "                count += j - i\n",
    "\n",
    "\t        # 最后补上等于 num 的部分\n",
    "            total += num * (k - count)\n",
    "            return total\n",
    "\n",
    "\n",
    "        return (getSum(right) - getSum(left - 1)) % MODULO\n",
    "\n",
    "\n",
    "\n",
    "# 排序\n",
    "# O(n^2logn) O(n^2)\n",
    "class Solution3:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        sumsLength = n * (n + 1) // 2\n",
    "        sums = list()\n",
    "        index = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                total += nums[j]\n",
    "                sums.append(total)\n",
    "        \n",
    "        sums.sort()\n",
    "        ans = sum(sums[left-1:right]) % MOD\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        inf = 10 ** 10\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = [0] * (right + 1)\n",
    "        # 创建 n 个指针\n",
    "        # 每个指针指向对应的值\n",
    "        pointer = [i for i in range(n)]\n",
    "        pointerAns = list(nums)\n",
    "        i = 1\n",
    "        c = defaultdict(int)\n",
    "        for item in nums:\n",
    "            c[item] += 1\n",
    "\n",
    "        while i < right + 1:\n",
    "            # 每次取最小的值\n",
    "            m = min(pointerAns)\n",
    "            for _ in range(c[m]):\n",
    "                if i < right + 1:\n",
    "                    res[i] = m\n",
    "                i += 1\n",
    "\n",
    "            # 更新最小值\n",
    "            for index, item in enumerate(pointerAns):\n",
    "                if item == m:\n",
    "                    pointer[index] += 1\n",
    "                    oldAns = pointerAns[index]\n",
    "                    if pointer[index] < n:\n",
    "                        pointerAns[index] += nums[pointer[index]]\n",
    "                        pointerAns[index] %= MOD\n",
    "                        c[oldAns] -= 1\n",
    "                        c[pointerAns[index]] += 1\n",
    "                    else:\n",
    "                        pointerAns[index] = inf\n",
    "                        c[oldAns] -= 1\n",
    "                        \n",
    "        l = s = 0\n",
    "        for index, item in enumerate(res):\n",
    "            if index < left:\n",
    "                l += item \n",
    "                l %= MOD\n",
    "            s += item\n",
    "            s %= MOD\n",
    "        \n",
    "\n",
    "        return (s - l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        inf = 10 ** 10\n",
    "        MOD = 10 ** 9 + 7\n",
    "        '''\n",
    "        [1,2,3,4]\n",
    "        1 2 3 4\n",
    "        2 3 4\n",
    "        3 4\n",
    "        4\n",
    "        '''\n",
    "        res = [0] * (right + 1)\n",
    "        # 创建 n 个指针\n",
    "        # 每个指针指向对应的值\n",
    "        pointer = [i for i in range(n)]\n",
    "        pointerAns = list(nums)\n",
    "        i = 1\n",
    "        while i < right + 1:\n",
    "            # 每次取最小的值\n",
    "            c = Counter(pointerAns)\n",
    "            m = min(pointerAns)\n",
    "            for _ in range(c[m]):\n",
    "                if i < right + 1:\n",
    "                    res[i] = m\n",
    "                i += 1\n",
    "\n",
    "            # 更新最小值\n",
    "            for index, item in enumerate(pointerAns):\n",
    "                if item == m:\n",
    "                    pointer[index] += 1\n",
    "                    if pointer[index] < n:\n",
    "                        pointerAns[index] += nums[pointer[index]]\n",
    "                        pointerAns[index] %= MOD\n",
    "                    else:\n",
    "                        pointerAns[index] = inf\n",
    "        l = s = 0\n",
    "        for index, item in enumerate(res):\n",
    "            if index < left:\n",
    "                l += item \n",
    "                l %= MOD\n",
    "            s += item\n",
    "            s %= MOD\n",
    "        \n",
    "\n",
    "        return (s - l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        inf = 10 ** 10\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = [0] * (right + 1)\n",
    "        '''\n",
    "        [1, 3, 4 ,5]\n",
    "\n",
    "        1 3 6 10\n",
    "        2 5 9\n",
    "        3 7\n",
    "        4\n",
    "\n",
    "        '''\n",
    "        # 所有的答案一定是 从每个元素开始从后面累加 这是子数组的定义 \n",
    "        # 根据上面的图 所有子数组就是上面所有的倒三角\n",
    "        # 创建 n 个指针 每个指针指向数组每个位置\n",
    "        pointer = [i for i in range(n)]\n",
    "        # 记录每个指针的当前累计的和\n",
    "        pointerAns = list(nums)\n",
    "        i = 1\n",
    "        c = defaultdict(int)\n",
    "        for item in nums:\n",
    "            c[item] += 1\n",
    "\n",
    "        while i < right + 1:\n",
    "            # 每次取最小的值\n",
    "            m = min(pointerAns)\n",
    "            for _ in range(c[m]):\n",
    "                if i < right + 1: res[i] = m\n",
    "                i += 1\n",
    "\n",
    "            # 更新最小值\n",
    "            for index, item in enumerate(pointerAns):\n",
    "                if item == m:\n",
    "                    pointer[index] += 1\n",
    "                    oldAns = pointerAns[index]\n",
    "                    if pointer[index] < n:\n",
    "                        pointerAns[index] += nums[pointer[index]]\n",
    "                        pointerAns[index] %= MOD\n",
    "                        c[oldAns] -= 1\n",
    "                        c[pointerAns[index]] += 1\n",
    "                    else:\n",
    "                        # 如果达到了子数组的末尾 将元素设置为空\n",
    "                        pointerAns[index] = inf\n",
    "                        c[oldAns] -= 1\n",
    "                        \n",
    "        l = s = 0\n",
    "        for index, item in enumerate(res):\n",
    "            if index < left:\n",
    "                l += item \n",
    "                l %= MOD\n",
    "            s += item\n",
    "            s %= MOD\n",
    "        \n",
    "\n",
    "        return (s - l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        mapping = {}\n",
    "        for i in range(n):\n",
    "            pre = nums[i]\n",
    "            if(pre not in mapping):\n",
    "                mapping[pre] = 1\n",
    "            else:\n",
    "                mapping[pre] += 1\n",
    "            for j in range(i+1,n):\n",
    "                pre += nums[j]\n",
    "                if(pre not in mapping):\n",
    "                    mapping[pre] = 1\n",
    "                else:\n",
    "                    mapping[pre] += 1\n",
    "        nums_sort = sorted(mapping.keys())\n",
    "        result = 0\n",
    "        cnt = 0\n",
    "        for num in nums_sort:\n",
    "            cnt += mapping[num]\n",
    "            if(cnt < left):\n",
    "                continue\n",
    "            elif(left <= cnt < right):\n",
    "                result += num * (cnt-left+1)\n",
    "                left = cnt+1\n",
    "            else:\n",
    "                result += num * (right-left+1)\n",
    "                break\n",
    "            result = result % (10**9+7)\n",
    "        return result % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        mapping = {}\n",
    "        for i in range(n):\n",
    "            pre = nums[i]\n",
    "            if(pre not in mapping):\n",
    "                mapping[pre] = 1\n",
    "            else:\n",
    "                mapping[pre] += 1\n",
    "            for j in range(i+1,n):\n",
    "                pre += nums[j]\n",
    "                if(pre not in mapping):\n",
    "                    mapping[pre] = 1\n",
    "                else:\n",
    "                    mapping[pre] += 1\n",
    "        nums_sort = sorted(mapping.keys())\n",
    "        result = 0\n",
    "        cnt = 0\n",
    "        for num in nums_sort:\n",
    "            cnt += mapping[num]\n",
    "            if(cnt < left):\n",
    "                continue\n",
    "            elif(left <= cnt < right):\n",
    "                result += num * (cnt-left+1)\n",
    "                left = cnt+1\n",
    "            else:\n",
    "                result += num * (right-left+1)\n",
    "                break\n",
    "            result = result % (10**9+7)\n",
    "        return result % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        mapping = {}\n",
    "        for i in range(n):\n",
    "            pre = nums[i]\n",
    "            if(pre not in mapping):\n",
    "                mapping[pre] = 1\n",
    "            else:\n",
    "                mapping[pre] += 1\n",
    "            for j in range(i+1,n):\n",
    "                pre += nums[j]\n",
    "                if(pre not in mapping):\n",
    "                    mapping[pre] = 1\n",
    "                else:\n",
    "                    mapping[pre] += 1\n",
    "        nums_sort = sorted(mapping.keys())\n",
    "        result = 0\n",
    "        cnt = 0\n",
    "        for num in nums_sort:\n",
    "            cnt += mapping[num]\n",
    "            if(cnt < left):\n",
    "                continue\n",
    "            elif(left <= cnt < right):\n",
    "                result += num * (cnt-left+1)\n",
    "                left = cnt+1\n",
    "            else:\n",
    "                result += num * (right-left+1)\n",
    "                break\n",
    "            result = result % (10**9+7)\n",
    "        return result % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        # left -= 1\n",
    "        # right -= 1\n",
    "        mapping = {}\n",
    "        for i in range(n):\n",
    "            pre = nums[i]\n",
    "            if(pre not in mapping):\n",
    "                mapping[pre] = 1\n",
    "            else:\n",
    "                mapping[pre] += 1\n",
    "            for j in range(i+1,n):\n",
    "                pre += nums[j]\n",
    "                if(pre not in mapping):\n",
    "                    mapping[pre] = 1\n",
    "                else:\n",
    "                    mapping[pre] += 1\n",
    "        nums_sort = sorted(mapping.keys())\n",
    "        result = 0\n",
    "        cnt = 0\n",
    "        for num in nums_sort:\n",
    "            cnt += mapping[num]\n",
    "            if(cnt < left):\n",
    "                continue\n",
    "            elif(left <= cnt < right):\n",
    "                result += num * (cnt-left+1)\n",
    "                left = cnt+1\n",
    "            else:\n",
    "                result += num * (right-left+1)\n",
    "                break\n",
    "        return result % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        l = []\n",
    "        for i in range(len(nums)):\n",
    "            for s in accumulate(nums[i:]):\n",
    "                heappush(l, s)\n",
    "        ans = 0\n",
    "        for _ in range(left - 1):\n",
    "            heappop(l)\n",
    "        for _ in range(right - left + 1):\n",
    "            ans += heappop(l)\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        l = []\n",
    "        for i in range(n):\n",
    "            for s in accumulate(nums[i:]):\n",
    "                heappush(l, s)\n",
    "        ans = 0\n",
    "        for _ in range(left - 1):\n",
    "            heappop(l)\n",
    "        for _ in range(right - left + 1):\n",
    "            ans += heappop(l)\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        dp = [i for i in range(len(nums))]\n",
    "        pre = [i for i in nums]\n",
    "        res = []\n",
    "\n",
    "        idx = 0\n",
    "        while True:\n",
    "            min_num = min(pre)\n",
    "            idx += 1\n",
    "            if idx >= left:\n",
    "                res.append(min_num)\n",
    "            if idx == right:\n",
    "                return sum(res)%(pow(10, 9)+7)\n",
    "            for j in range(len(pre)):\n",
    "                if pre[j] == min_num:\n",
    "                    dp[j] += 1\n",
    "                    if dp[j] < len(nums):\n",
    "                        pre[j] += nums[dp[j]]\n",
    "                    else:\n",
    "                        pre[j] = float('inf')\n",
    "                    break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        heap = []\n",
    "        for i in range(len(nums)):\n",
    "            heapq.heappush(heap, (nums[i], i))\n",
    "        cnt = 0\n",
    "        res = []\n",
    "        while heap:\n",
    "            num, idx = heapq.heappop(heap)\n",
    "            cnt += 1\n",
    "            if cnt >= left:\n",
    "                res.append(num)\n",
    "            if cnt == right:\n",
    "                return sum(res)%(pow(10, 9)+7)\n",
    "            if idx+1 < len(nums):\n",
    "                heapq.heappush(heap, (num+nums[idx+1], idx+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        sum_nums = []\n",
    "        for i in range(len(nums)):\n",
    "            a=nums[i]\n",
    "            sum_nums.append(a)\n",
    "            for j in range(i-1,-1,-1):\n",
    "                a = a+nums[j]\n",
    "                sum_nums.append(a)\n",
    "        sum_nums.sort()\n",
    "        res=0\n",
    "        for i in range(left-1,right):\n",
    "            res+=sum_nums[i]\n",
    "        return int(res%(1e9 + 7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        sums = []\n",
    "        pre = [0] * n\n",
    "\n",
    "        s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s += x\n",
    "            pre[i] = s\n",
    "            sums.append(s)\n",
    "            for j in range(i):\n",
    "                sums.append(pre[i] - pre[j])\n",
    "        sums.sort()\n",
    "        s = 0\n",
    "        for i, x in enumerate(sums):\n",
    "            sums[i] = sums[i] + s\n",
    "            sums[i] %= mod\n",
    "            s += x\n",
    "        if left == 1:\n",
    "            return sums[right - 1]\n",
    "        else:\n",
    "            print(sums[right - 1], sums[left - 2])\n",
    "            return sums[right - 1] - sums[left - 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            v = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                v += nums[j]\n",
    "                ans.append(v)\n",
    "\n",
    "        ans.sort()\n",
    "        res = 0\n",
    "        for i in range(left, right + 1):\n",
    "            res += ans[i - 1]\n",
    "            res %= mod\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        s = []\n",
    "        p = 0\n",
    "        while p < n:\n",
    "            q = p + 1\n",
    "            temp = nums[p]\n",
    "            while q < n:\n",
    "                s.append(temp)\n",
    "                temp += nums[q]\n",
    "                q += 1\n",
    "            s.append(temp)\n",
    "            p += 1\n",
    "        s.sort()\n",
    "        res = 0\n",
    "        for i in range(left - 1, right):\n",
    "            res = (res + s[i]) % int(1e9 + 7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        pre = [0]\n",
    "        for num in nums:\n",
    "            pre.append(pre[-1]+num)\n",
    "\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                stack.append(pre[j] - pre[i])\n",
    "        stack.sort()\n",
    "        ans = 0\n",
    "        for i in range(left - 1, right):\n",
    "            ans += stack[i]\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "\n",
    "        # 计算前缀和\n",
    "        prefixSum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            prefixSum[i + 1] = prefixSum[i] + nums[i]\n",
    "\n",
    "        # 计算所有子数组的和\n",
    "        subarraySums = []\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(i, n + 1):\n",
    "                subarraySums.append(prefixSum[j] - prefixSum[i - 1])\n",
    "\n",
    "        # 对子数组的和进行排序\n",
    "        subarraySums.sort()\n",
    "\n",
    "        # 返回指定范围内的和，注意下标从 1 开始\n",
    "        result = 0\n",
    "        for k in range(left - 1, right):\n",
    "            result = (result + subarraySums[k]) % MOD\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        acc=list(accumulate(nums, initial=0))\n",
    "        n=len(nums)\n",
    "        newa = [0]*(n*(n+1)//2)\n",
    "        for k,(i,j) in enumerate(combinations(range(n+1), r=2)):\n",
    "            newa[k] = acc[j] - acc[i]\n",
    "        newa.sort()\n",
    "        m=10**9+7\n",
    "        return sum(newa[i] for i in range(left-1, right)) % m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        l = len(nums)\n",
    "        preSum = [0] * l\n",
    "        preSum[0] = nums[0]\n",
    "        pre = {-1:0}\n",
    "        for i in range(1,l):\n",
    "            preSum[i] = preSum[i-1] + nums[i]\n",
    "        for j in range(l):\n",
    "            pre[j] = preSum[j]\n",
    "        subSum = []\n",
    "        for i in range(-1,l-1):\n",
    "            for j in range(i+1,l):\n",
    "                subSum.append(pre[j]-pre[i])\n",
    "        ans = 0\n",
    "        subSum.sort()\n",
    "        for k in range(left-1,right):\n",
    "            ans += subSum[k]\n",
    "        return ans % 1000000007\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        preSum = [0] * (n + 1)\n",
    "        s = 10 ** 9 + 7\n",
    "        for i in range(1,n + 1):\n",
    "            preSum[i] = (nums[i - 1] + preSum[i-1]) % s\n",
    "        childSum = []\n",
    "        for i in range(1,n + 1):\n",
    "            for j in range(i,n + 1):\n",
    "                childSum.append((preSum[j] - preSum[i - 1]) % s)\n",
    "        childSum.sort()\n",
    "        sum = 0\n",
    "        for i in range(left - 1,right):\n",
    "            sum = sum + childSum[i] % s\n",
    "            sum %= s\n",
    "        return sum % s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        l = len(nums)\n",
    "        preSum = [0] * l\n",
    "        preSum[0] = nums[0]\n",
    "        pre = {-1:0}\n",
    "        for i in range(1,l):\n",
    "            preSum[i] = preSum[i-1] + nums[i]\n",
    "        for j in range(l):\n",
    "            pre[j] = preSum[j]\n",
    "        subSum = []\n",
    "        for i in range(-1,l-1):\n",
    "            for j in range(i+1,l):\n",
    "                subSum.append(pre[j]-pre[i])\n",
    "        ans = 0\n",
    "        subSum.sort()\n",
    "        for k in range(left-1,right):\n",
    "            ans += subSum[k]\n",
    "        return ans % 1000000007\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            res.append(nums[i])\n",
    "            for j in range(i+1,n):\n",
    "                res.append(res[-1] + nums[j])\n",
    "        res.sort()\n",
    "        ans = sum(res[left - 1 : right]) % (10**9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        sums = []\n",
    "        for i in range(len(nums)):\n",
    "            sums += list(itertools.accumulate(nums[i:]))\n",
    "        sums.sort()\n",
    "        return sum(sums[left-1:right]) % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        sums = []\n",
    "        next_sums = []\n",
    "        for num in nums:\n",
    "            temp = []\n",
    "            temp.append(num)\n",
    "            for n in next_sums:\n",
    "                temp.append(n+num)\n",
    "            next_sums = temp\n",
    "            sums.extend(next_sums)\n",
    "        sums.sort()\n",
    "        return sum(sums[left-1:right]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        s = []\n",
    "        for i in range(len(nums)):\n",
    "            res = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                res += nums[j]\n",
    "                s.append(res)\n",
    "        s.sort()\n",
    "        return sum(s[left-1: right]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        l = []\n",
    "        for i in range(n):\n",
    "            for s in accumulate(nums[i:]):\n",
    "                l.append(s)\n",
    "        l.sort()\n",
    "        return sum(l[left-1:right]) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        sums = list()\n",
    "        MOD = 10 ** 9 + 7\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if i == j:\n",
    "                    sums.append(nums[i])\n",
    "                else:\n",
    "                    tmp = sums[-1] + nums[j]\n",
    "                    sums.append(tmp)\n",
    "        sums.sort()\n",
    "        # print(sums)\n",
    "        return sum(sums[left-1: right]) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        arr = []\n",
    "        for i in range(n):\n",
    "            cur_sum = 0\n",
    "            for j in range(i, n):\n",
    "                cur_sum+=nums[j]\n",
    "                arr.append(cur_sum)\n",
    "        arr.sort()\n",
    "        # print(arr)\n",
    "        # print(arr[left-1:right])\n",
    "        return sum(arr[left-1:right])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        # length = len(nums)\n",
    "        result_list = []\n",
    "        moudle = 10**9 + 7\n",
    "        result = 0\n",
    "        for i in range(0,n):\n",
    "            total = 0\n",
    "            for j in range(i,n):\n",
    "                total += nums[j]\n",
    "                result_list.append(total)\n",
    "        result_list.sort()\n",
    "        result = sum(result_list[left-1:right])%moudle\n",
    "        return result\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        my_list = [];\n",
    "        i = 0\n",
    "        j = 0\n",
    "        acc = 0\n",
    "        for i in range(n):\n",
    "            my_list.append(nums[i])\n",
    "            acc = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                acc += nums[j]\n",
    "                my_list.append(acc)\n",
    "        my_list.sort()\n",
    "        return sum(my_list[left - 1:right]) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        all_sum = []\n",
    "        #前缀和\n",
    "        for i in range(n):\n",
    "            #temp中记录了以i为起始下标的所有子区间的和\n",
    "            temp = [0]\n",
    "            for j in range(i,n):\n",
    "                val = temp[-1]+nums[j]\n",
    "                all_sum.append(val)\n",
    "                temp.append(val)\n",
    "        all_sum.sort()\n",
    "        # print(all_sum)\n",
    "        return sum(all_sum[left-1:right])%(10**9+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        prefixsum = [0] * n\n",
    "        prefixsum[0] = nums[0]\n",
    "        newNums = [nums[0]]\n",
    "        for i in range(1,n):\n",
    "            prefixsum[i] = prefixsum[i-1] + nums[i]\n",
    "            newNums.append(prefixsum[i])\n",
    "            for j in range(i):\n",
    "                newNums.append(prefixsum[i] - prefixsum[j])\n",
    "        newNums.sort()\n",
    "        ans = sum(newNums[left-1:right])\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        sums = []\n",
    "        next_sums = []\n",
    "        for num in nums:\n",
    "            next_sums = [s + num for s in next_sums]\n",
    "            next_sums.append(num)\n",
    "            sums.extend(next_sums)\n",
    "        sums.sort()\n",
    "        return sum(sums[left-1:right]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        resList = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                resList.append(sum(nums[i:j + 1]))\n",
    "        resList.sort()\n",
    "        return sum(resList[left - 1:right]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        pre = [0]\n",
    "        cur = []\n",
    "        for num in nums:\n",
    "            pre.append(pre[-1] + num)\n",
    "        for i in range(len(pre) - 1):\n",
    "            for j in range(i+1, len(pre)):\n",
    "                cur.append(pre[j] - pre[i])\n",
    "        cur.sort()\n",
    "        return sum(cur[left-1:right]) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        ans = []\n",
    "        mod = int(1e9+7)\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                ans.append(sum(nums[i:j+1]))\n",
    "        ans.sort()\n",
    "        return sum(ans[left-1:right]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        #sumsLength = n * (n + 1) // 2\n",
    "        sums = list()\n",
    "        #index = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                total += nums[j]\n",
    "                sums.append(total)\n",
    "        \n",
    "        sums.sort()\n",
    "        ans = sum(sums[left-1:right]) % MODULO\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        n = len(nums)\n",
    "        arr = [0]\n",
    "        for i in nums:\n",
    "            arr.append(arr[-1]+i)\n",
    "        l = []\n",
    "        for i in range(n+1):\n",
    "            for j in range(i+1,n+1):\n",
    "                l.append(arr[j] - arr[i])\n",
    "        l.sort()\n",
    "        return sum(l[left-1:right])% (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        my_list = [];\n",
    "        i = 0\n",
    "        j = 0\n",
    "        acc = 0\n",
    "        for a in nums:\n",
    "            my_list.append(nums[i])\n",
    "            acc = nums[i]\n",
    "            j = i + 1\n",
    "            while j < len(nums):\n",
    "                acc += nums[j]\n",
    "                my_list.append(acc)\n",
    "                j += 1\n",
    "            i += 1\n",
    "        my_list.sort()\n",
    "        return sum(my_list[left - 1:right]) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        t=0\n",
    "        presum=[]\n",
    "        for i in range(len(nums)):\n",
    "            t+=nums[i]\n",
    "            presum.append(t)\n",
    "        rangesum=presum\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                rangesum.append(presum[j]-presum[i])\n",
    "        rangesum.sort()\n",
    "        return sum(rangesum[left-1:right])%(10**9+7)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        sumsLength = n * (n + 1) // 2\n",
    "        sums = list()\n",
    "        index = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                total += nums[j]\n",
    "                sums.append(total)\n",
    "        \n",
    "        sums.sort()\n",
    "        ans = sum(sums[left-1:right]) % MODULO\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        from itertools import accumulate\n",
    "        arr=[]\n",
    "        for i in range(len(nums)):\n",
    "            tmp=list(accumulate(nums[i:]))\n",
    "            arr+=tmp\n",
    "        arr.sort()\n",
    "        return sum(arr[left-1:right])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        lis = []\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n+1):\n",
    "                lis.append(sum(nums[i:j]))\n",
    "        lis.sort()\n",
    "        ans = sum(lis[left-1:right])\n",
    "        ans = ans%(10 **9+7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            stack.append(nums[i])\n",
    "            for j in range(i+1, n):\n",
    "                stack.append(stack[-1] + nums[j])\n",
    "        stack.sort()\n",
    "        sums = sum(stack[left-1:right])\n",
    "        return sums % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                cnt += nums[j]\n",
    "                ans.append(cnt)\n",
    "        ans.sort()\n",
    "        return int(sum(ans[left-1:right])%(1e9+7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        new_nums = []\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                new_nums.append(sum(nums[i : j + 1]))\n",
    "        new_nums.sort()\n",
    "        return sum(new_nums[left-1:right]) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        temp = []\n",
    "        for i,v in enumerate(nums):\n",
    "            cao = i+1\n",
    "            while cao<=n:\n",
    "                temp.append(sum(nums[i:cao]))\n",
    "                cao+=1\n",
    "        temp.sort()\n",
    "        return sum(temp[left-1:right])%1000000007\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        acc = list(accumulate(nums, initial=0))\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                res.append(acc[j + 1] - acc[i])\n",
    "        res.sort()\n",
    "        return sum(res[left - 1: right]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        num = []\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                num.append(sum(nums[i:j]))\n",
    "        num.sort()\n",
    "        return sum(num[left-1:right]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] + nums[i]\n",
    "        lst = []\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                lst.append(pre[j + 1] - pre[i])\n",
    "        lst.sort()\n",
    "        return sum(lst[left - 1: right]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res += list(itertools.accumulate(nums[i:]))\n",
    "        res.sort()\n",
    "        return sum(res[left - 1: right]) % (10 ** 9 + 7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        def helper(nums, length):\n",
    "            total = sum(nums[0: length])\n",
    "            cur = length\n",
    "            i = 0\n",
    "            res.append(total)\n",
    "            while cur < len(nums):\n",
    "                total -= nums[i]\n",
    "                total += nums[cur]\n",
    "                cur += 1\n",
    "                i += 1\n",
    "                res.append(total)\n",
    "        \n",
    "        mod = 10 ** 9 + 7\n",
    "        res = []\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            helper(nums, i)\n",
    "        res.sort()\n",
    "        return sum(res[left - 1: right]) % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        resList = []\n",
    "        for i in range(len(nums)):\n",
    "            resList += list(itertools.accumulate(nums[i:]))\n",
    "        resList.sort()\n",
    "        return sum(resList[left - 1:right]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        N = 10 ** 9 + 7\n",
    "        l = len(nums)\n",
    "        prefix = [0] * (l + 1)\n",
    "        for i in range(l):\n",
    "            prefix[i + 1] = prefix[i] + nums[i]\n",
    "        temp = []\n",
    "        for i in range(l):\n",
    "            for j in range(i + 1, l + 1):\n",
    "                temp.append(prefix[j] - prefix[i])\n",
    "        temp.sort()\n",
    "        return sum(temp[left - 1: right]) % N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                res.append(sum(nums[i:j + 1]))\n",
    "        res.sort()\n",
    "        return sum(res[left - 1: right]) % (10 ** 9 + 7)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        ans=[]\n",
    "        for i in range(len(nums)):\n",
    "            ans.append(nums[i])\n",
    "            for j in nums[i+1:]:\n",
    "                ans.append(ans[-1]+j)\n",
    "        ans.sort()\n",
    "        return sum(ans[left-1:right])%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# * 二分查找 + 双指针 ?\n",
    "# O(nlogS) O(n)\n",
    "# https://leetcode.cn/problems/range-sum-of-sorted-subarray-sums/solution/zi-shu-zu-he-pai-xu-hou-de-qu-jian-he-by-leetcode-/\n",
    "# https://leetcode.cn/problems/range-sum-of-sorted-subarray-sums/solution/-by-mkdir700-l90o/\n",
    "class Solution1:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MODULO = 10**9 + 7\n",
    "        prefixSums = [0]\n",
    "        for i in range(n):\n",
    "            prefixSums.append(prefixSums[-1] + nums[i])\n",
    "        \n",
    "        prefixPrefixSums = [0]\n",
    "        for i in range(n):\n",
    "            prefixPrefixSums.append(prefixPrefixSums[-1] + prefixSums[i + 1])\n",
    "\n",
    "        def getCount(x: int) -> int:\n",
    "            count = 0\n",
    "            j = 1\n",
    "            # 遍历虚拟矩阵的每一层，统计满足条件的个数\n",
    "            for i in range(n):\n",
    "\t            # i 在不断增长，所以 prefixSums[i] 一直表示都是当前层的第一个元素\n",
    "                while j <= n and prefixSums[j] - prefixSums[i] <= x:\n",
    "\t                # 符合条件就右移\n",
    "                    j += 1\n",
    "\n",
    "                j -= 1\n",
    "                count += j - i\n",
    "\n",
    "            return count\n",
    "\n",
    "\n",
    "        def getKth(k: int) -> int:\n",
    "\t        # 这里整个二分查找就是求左边界\n",
    "\t\t\t# 即找到第一个满足 count == k 的值（使count == k的最小值）\n",
    "            left, right = 0, prefixSums[n]\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                count = getCount(mid)\n",
    "                if count < k:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "\n",
    "            return left\n",
    "\n",
    "\n",
    "        def getSum(k: int) -> int:\n",
    "            num = getKth(k)\n",
    "            total, count = 0, 0\n",
    "            j = 1\n",
    "            # 遍历“虚拟矩阵”的每一层\n",
    "            for i in range(n):\n",
    "                while j <= n and prefixSums[j] - prefixSums[i] < num:\n",
    "                    j += 1\n",
    "\n",
    "                # 当前 j 位置的元素是 i 行 第 1 个大于等于 num 的值\n",
    "                # 我们要找的是最后一个小于 num 的元素，所以 -1\n",
    "                # 确定区间的右边界 j\n",
    "                j -= 1\n",
    "\n",
    "                # 计算区间和\n",
    "                total += prefixPrefixSums[j] - prefixPrefixSums[i] - prefixSums[i] * (j - i)\n",
    "                # 记录当前行符合条件的个数\n",
    "                count += j - i\n",
    "\n",
    "\t        # 最后补上等于 num 的部分\n",
    "            total += num * (k - count)\n",
    "            return total\n",
    "\n",
    "\n",
    "        return (getSum(right) - getSum(left - 1)) % MODULO\n",
    "\n",
    "\n",
    "\n",
    "# 排序\n",
    "# O(n^2logn) O(n^2)\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        sumsLength = n * (n + 1) // 2\n",
    "        sums = list()\n",
    "        index = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            total = 0\n",
    "            for j in range(i, n):\n",
    "                total += nums[j]\n",
    "                sums.append(total)\n",
    "        \n",
    "        sums.sort()\n",
    "        ans = sum(sums[left-1:right]) % MOD\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        from itertools import accumulate\n",
    "        arr=[]\n",
    "        for i in range(len(nums)):\n",
    "            tmp=list(accumulate(nums[i:]))\n",
    "            arr+=tmp\n",
    "        arr.sort()\n",
    "        return sum(arr[left-1:right])%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        new = []\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            new.append(nums[i])\n",
    "            total = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                total += nums[j]\n",
    "                new.append(total)\n",
    "        new.sort()\n",
    "        return sum(new[left-1:right]) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        sumA = SortedList()\n",
    "        for i in range(n):\n",
    "            s = nums[i]\n",
    "            sumA.add(s)\n",
    "            for j in range(i+1,n):\n",
    "                s += nums[j]\n",
    "                sumA.add(s)\n",
    "        return sum(sumA[left-1:right]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:\n",
    "        lst = []\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums) + 1):\n",
    "                lst.append(sum(nums[i: j]))\n",
    "\n",
    "        lst = sorted(lst)\n",
    "\n",
    "        return sum(lst[left-1: right]) % (10**9 + 7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
